package my.algorithm.sort;

import org.apache.commons.lang.ArrayUtils;

/**
 * 冒泡排序改进（鸡尾酒排序）
 * @author xsw
 * @date 2018年9月27日
 */
public class CocktailSort {
	public static void main(String[] args) {
		int[] list = { 6, 5, 3, 1, 8, 7, 2, 4 };
		System.out.println(ArrayUtils.toString(list));
		sort(list);
//		sortBetter(list);
		System.out.println(ArrayUtils.toString(list));
	}
	// 分类 -------------- 内部比较排序
	// 数据结构 ---------- 数组
	// 最差时间复杂度 ---- O(n^2)
	// 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
	// 平均时间复杂度 ---- O(n^2)
	// 所需辅助空间 ------ O(1)
	// 稳定性 ------------ 稳定
	public static void sort(int[] list){
		if(list == null || list.length == 0) return ;
		int temp;
		int count = 0;
		for (int i = 0; i < list.length/2; i++) {
			//从左往右扫描，选出最大的元素放到右边
			for (int j = i; j < list.length - i -1; j++) {
				if(list[j] > list[j+1]){
					temp = list[j];
					list[j] = list[j+1];
					list[j+1] = temp;
				}
				count++;
			}
			//从右往左扫描，选出最小的元素放到左边
			for (int j = list.length - i -2; j > i; j--) {
				if(list[j] < list[j-1]){
					temp = list[j];
					list[j] = list[j-1];
					list[j-1] = temp;
				}
				count++;
			}
			System.out.println(i+"\t"+ArrayUtils.toString(list));
		}
		System.out.println("【比较次数】"+count);
	}
	
	/**
	 * 鸡尾酒算法优化：添加左右加标，标记上一次左右最后移动的边界在哪，如果从左到右扫描（从右到左扫描）没有改变右边界，则认为当前序列有序，退出排序
	 * @param list
	 */
	public static void sortBetter(int[] list){
		if(list == null || list.length == 0) return ;
		int temp;
		int right = list.length -1;
		int left = 0;
		int pos = 0;
		int count = 0;
		while (true) {
			pos = right;
			//从左往右扫描，选出最大的元素放到右边
			for (int j = left; j < right; j++) {
				if(list[j] > list[j+1]){
					temp = list[j];
					list[j] = list[j+1];
					list[j+1] = temp;
					pos = j;
				}
				count++;
			}
			if(pos == right) break;
			right = pos;
			pos = left;
			//从右往左扫描，选出最小的元素放到左边
			for (int j = right; j > left; j--) {
				if(list[j] < list[j-1]){
					temp = list[j];
					list[j] = list[j-1];
					list[j-1] = temp;
					pos = j;
				}
				count++;
			}
			if(pos == left) break;
			left = pos;
		}
		System.out.println("【比较次数】"+count);
	}
	
	
	
}
